Exercici 12 (Tasca 2).
(regular languages,
polynomial time,
membership problem)
La pertinença a un regular és decidible en temps polinòmic
Considereu el problema decisional següent: \mathtt{Pertinen\c{c}a_{Reg}}: \text{ donada una entrada $x\in \{0,1\}^*$ i $A$ un DFA, determinar si } x\in L(A).
Demostreu \mathtt{Pertinen\c{c}a_{Reg}} es pot decidir en temps polinòmic en |x| i la mida de A.